package com.zp.self.module.level_4_算法练习.数据结构.String;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_17_电话号码的字母组合 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_17_电话号码的字母组合().letterCombinations("23"));
        System.out.println(new 力扣_17_电话号码的字母组合().letterCombinations(""));
        System.out.println(new 力扣_17_电话号码的字母组合().letterCombinations("2"));
        System.out.println(new 力扣_17_电话号码的字母组合().letterCombinations("2345"));
        System.out.println(new 力扣_17_电话号码的字母组合().letterCombinations("6789"));
    }

    /**
    题目：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
     答案可以按 任意顺序 返回。
     给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

     示例 1：
     输入：digits = "23"
     输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

     示例 2：
     输入：digits = ""
     输出：[]

     示例 3：
     输入：digits = "2"
     输出：["a","b","c"]

    分析：【P 💜💜】
       1.简单循环完成  4个字母: 设置双数组 记录每个号码的字母情况
            --执行用时：5 ms, 在所有 Java 提交中击败了5.06%的用户
       2.回溯法： sb 不断的向下添加，到尽头加入list，然后回溯一下加入list.不断回溯
            --执行用时：1 ms, 在所有 Java 提交中击败了51.06%的用户
          优化：将list改为sb
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.
     **/
    public List<String> letterCombinations(String digits) {
        List<String> current = new ArrayList<>();
        if(digits.length()==0) return current;
        // 2.回溯法与
        char[][] zhiMu = new char[][]{{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'}
                ,{'m','o','n'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
        StringBuilder sb = new StringBuilder();
        dfs(digits,zhiMu,0,sb,current);
        return  current;

        //  1.简单循环完成  4个字母: 设置双数组 记录每个号码的字母情况
       /* char[][] zhiMu = new char[][]{{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'}
        ,{'m','o','n'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};

        List<String> current = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) {
            char[] arr = zhiMu[digits.charAt(i)-'2'];
            if(current.isEmpty()){
                for (int j = 0; j < arr.length; j++)
                    current.add(String.valueOf(arr[j]));
            }else {
                List<String> pro = new ArrayList<>();
                for (int j = 0; j < arr.length; j++) {
                    for (String re : current)
                        pro.add(re+arr[j]) ;
                }
                current=pro;
            }
        }
        return current;*/
    }

    private void dfs(String digits, char[][] zhiMu, int index,StringBuilder sb, List<String> current) {
        if(sb.length()==digits.length()){
            current.add(sb.toString());
        }else {
            int at = digits.charAt(index)-'2';
            for (int j = 0; j < zhiMu[at].length; j++) {
                sb.append(zhiMu[at][j]);
                dfs(digits,zhiMu,index+1,sb,current);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}
